/**
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */

/**
 * 前序遍历-递归 
 */
const preOrder = (root, reslut=[]) => {
  if(!root) return reslut;
  reslut.push(root.val);
  preOrder(root.left, reslut);
  preOrder(root.right, reslut);
  return reslut;
}

/**
 * 中序遍历-递归
 */
const inOrder = (root, result=[]) => {
  if(!root) return result;
  inOrder(root.left, result);
  result.push(root.val);
  inOrder(root.right, result);
  return result;
}

/**
 * 后序遍历-递归
 */
const postOrder = (root, result=[]) => {
  if(!root) return result;
  postOrder(root.left, result);
  postOrder(root.right, result);
  result.push(root.val);
  return result;
}
/**
 * 层序遍历-递归
 * 层序遍历就是树的数组表示
 * 队列queue res加入当前root后，左右节点都放入队列
 */
const levelOrder = (root, result=[]) => {
  if(!root) return result;
  const queue = [root];
  while(queue.length) {
    const node = queue.shift();
    result.push(node.val);
    if(node.left) queue.push(node.left);
    if(node.right) queue.push(node.right);
  }
  return result;
}
/**
 * 层序遍历，每一层都用一个数组表示
 * 输入：root = [3,9,20,null,null,15,7]
 * 输出：[[3],[9,20],[15,7]]
 */
import arrayToTree from './0-数组转为二叉树.js'
const levelOrder2 = (rootArr, result = []) => {
  const root = Array.isArray(rootArr) ? arrayToTree(rootArr) : rootArr;
  if (!root) return result;
  const queue = [root];
  while (queue.length) {
    const level = [];
    const size = queue.length;
    for (let i = 0; i < size; i++) {
      const node = queue.shift();
      level.push(node.val);
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    result.push(level);
  }
  return result;
};
/**
 * 二叉树的锯齿形层序遍历
输入：root = [3,9,20,null,null,15,7]
输出：[[3],[20,9],[15,7]]
 */
var zigzagLevelOrder = function(root) {
  if(!root) return []
  const res = []
  const queue = [root]
  let index = 0
  while(queue.length) {
    const size = queue.length
    const level = []
    for(let i=0;i<size;i++) {
      const node = queue.shift()
      node.left && queue.push(node.left)
      node.right && queue.push(node.right)
      level.push(node.val)
    }
    res.push(index&1 ? level.reverse(): level)
    index++
  }
  return res
};
/**
  1
 2 3
4 5 6 7
 */
const root = {
  val: 1,
  left: {
    val: 2,
    left: {
      val: 4,
    },
    right: {
      val: 5,
    }
  },
  right: {
    val: 3,
    left: {
      val: 6,
    },
    right: {
      val: 7,
    }
  }
}
// console.log('preOrder', JSON.stringify(preOrder(root)));
// console.log('inOrder', JSON.stringify(inOrder(root)));
// console.log('postOrder', JSON.stringify(postOrder(root)));
// console.log('levelOrder', JSON.stringify(levelOrder(root)));
const root_levelOrder2 = [3,9,20,null,null,15,7]
// console.log('levelOrder2', JSON.stringify(levelOrder2(root_levelOrder2)));
console.log('zigzagLevelOrder', JSON.stringify(zigzagLevelOrder(root)));